package com.test.ita;

import java.util.*;

/**
 * Created by IntelliJ IDEA.
 * User: gpss
 * Date: 7/22/11
 * Time: 3:55 PM
 * To change this template use File | Settings | File Templates.
 */
public class RebusGenerator {
    /**
     * Collects all unique set of pictures associated with the given word
     *
     * @param word
     * @return HashSet<String> containing unique pictures
     */
    private HashSet<String> findUniquePictureSet(String word) {
        HashSet<String> unionSet = new HashSet<String>();
        if (word == null || word.length() < 1) return unionSet; //empty set
        char[] combChar = word.toCharArray();
        for (Character c : combChar) {
            HashSet<String> charPicSet = Utils.dictionary.get((Character) Character.toLowerCase(c));
            unionSet.addAll(charPicSet);
        }
        return unionSet;
    }

    /**
     * comparator : used for sorting
     */
    class CostComparator implements Comparator<CostBean> {
        public int compare(CostBean bean1, CostBean bean2) {
            return bean1.getCost() - bean2.getCost();
        }
    }

    /**
     * filters pictures based on levenshtein distance (cost)
     *
     * @param word
     * @param bigPicSet
     * @return list of pictures with associated cost, only pictures with least distance are returned
     */
    private List<CostBean> filterSmallestLDSet(String word, HashSet<String> bigPicSet) {
        ArrayList<CostBean> smallPicSet = new ArrayList<CostBean>();
        Distance levDist = new Distance();
        for (Iterator it = bigPicSet.iterator(); it.hasNext(); ) {
            String pic = ((String) it.next()).trim();
            int c = levDist.LD(word, pic);
//            System.out.println("Word : "+word+" pic : "+pic+" cost : "+c);
            smallPicSet.add(new CostBean(pic, c));
        }

        Collections.sort(smallPicSet, new CostComparator());
        // collects top low cost items
        int i = 0;
        int min = 0;
        if (smallPicSet.size() > 0) {
            min = smallPicSet.get(0).getCost();
        }
        while (min == smallPicSet.get(i).getCost()) {
            i++;
        }
        return smallPicSet.subList(0, i);//Math.min(smallPicSet.size() > 4 ? 4 : i,i)
    }

    /**
     * for a given word and a picture, Longest Common Subsequence (LCS) is computed
     * for every such combination a RebusNode is made
     *
     * @param word
     * @param picSet
     * @return
     */
    //todo if costs are equal, list of rebus nodes should be returned.
    private ArrayList<RebusNode> findBestRebusPicture(String word, HashSet<String> picSet) {

        ArrayList<RebusNode> rnList = new ArrayList<RebusNode>();
        RebusNode rn = null;
        for (Iterator it = picSet.iterator(); it.hasNext(); ) {
            String pic = (String) it.next();
            LCSCell[][] lcsTable = Utils.computeLCS(word, pic);
            String lcs = Utils.printLCS(lcsTable, word, word.length(), pic.length()).reverse().toString();

            RebusNode nextRn = Utils.getRebusNode(word, lcs, pic);

            //we filter based on the cost if the list exceeds more than 10 elements
            if (picSet.size() > 10) {
                if (rn == null) {

                    rn = nextRn;
                    rnList.add(nextRn);
                } else if (nextRn.getCost() <= rn.getCost()) {
                    rn = nextRn;
                    rnList.add(nextRn);
                }

            } else {
                rnList.add(nextRn);
            }
        }
        return rnList;
    }

    //global value to be deleted :
//    int recursionDepth = 0;


    /**
     * Iteratively finds optimal RebusNode
     * Recursion stops when a) only one char left
     * b) cost is <= 2
     * c) of course no more chars left to encode into a picture
     *
     * @param rebus
     * @return optimal rebus
     */
    private RebusNode buildOptimalRebusNode(RebusNode rebus) {
        if (rebus == null || rebus.getRebus() == null
                || rebus.getRebus().length() <= 0
                || rebus.getRebus().startsWith(":")
                || Utils.findWordCost(rebus.getRebus()) <= 2) {
            return rebus;
        }
        //Rebus node will be in non picture state

        String word = rebus.getRebus();
        //only top level entry is considered to avoid programming complexity
        RebusNode optimalRebus = findBaseRebus(word).get(0);
        if (optimalRebus.getCost() >= rebus.getCost()) {
            return rebus;
        }
        //update with computed rebus/picture details of the rebus node
        rebus.setRebus(optimalRebus.getRebus());
        rebus.setCost(optimalRebus.getCost());
        rebus.setLeft(optimalRebus.getLeft());
        rebus.setRight(optimalRebus.getRight());

        if (rebus.getLeft() != null &&
                rebus.getLeft().getRebus() != null &&
                !"".equalsIgnoreCase(rebus.getLeft().getRebus()) &&
                rebus.getLeft().getRebus().length() > 1 &&
                rebus.getCost() > 2) {

            RebusNode lrn = buildOptimalRebusNode(rebus.getLeft());

            rebus.setLeft(lrn);
            //carry left rebus residue (cost & left out letters) details to right
            if (lrn.getRight() != null && lrn.getRight().getRebus() != null
                    && !lrn.getRight().getRebus().startsWith(":")) {
                rebus.setRight(new RebusNode(lrn.getRight().getRebus() + rebus.getRight().getRebus(),
                        rebus.getCost(), null, null));
                lrn.setRight(null);
            }
        }

        if (rebus.getRight() != null &&
                rebus.getRight().getRebus() != null &&
                !"".equalsIgnoreCase(rebus.getRight().getRebus()) &&
                rebus.getRight().getRebus().length() > 1 &&
                rebus.getCost() > 2) {

            RebusNode rrn = buildOptimalRebusNode(rebus.getRight());
            rebus.setRight(rrn);
        }

        return rebus;

    }

    /**
     * finds base rebus list
     *
     * @param word
     * @return ArrayList containing baseRebus nodes
     */
    private ArrayList<RebusNode> findBaseRebus(String word) {

        List<CostBean> smallPicSet = filterSmallestLDSet(word, findUniquePictureSet(word));
        HashSet<String> picSet = new HashSet<String>();
        int i = 1;
        for (CostBean picBean : smallPicSet) {
            i++;
            picSet.add(picBean.getItemString());
        }
        return findBestRebusPicture(word, picSet);
    }


//    private int rightWalkerRecursionDepth = 0;

    /**
     * Walks on the right edges
     *
     * @param rebusNode
     * @return residue string (to be concatenated to the right of base rebus
     */
    private String rebusWalker(RebusNode rebusNode) {
        StringBuffer residue = new StringBuffer();

        if (rebusNode.getRight() != null
                && rebusNode.getRight().getRebus() != null
                && !"".equalsIgnoreCase(rebusNode.getRight().getRebus())) {
            if (rebusNode.getRight().getRebus().startsWith(":")) {

                residue.append(rebusWalker(rebusNode.getRight()));
            } else {
                residue.append(rebusNode.getRight().getRebus());
                rebusNode.setRight(null);
            }
        }
        return residue.toString();
    }

    private int findMaxRightDepth(RebusNode rebusNode) {
        int rDepth = 0;
        if (rebusNode.getRight() != null
                && rebusNode.getRight().getRebus() != null
                && !"".equalsIgnoreCase(rebusNode.getRight().getRebus())) {
            if (rebusNode.getRight().getRebus().startsWith(":")) {

                rDepth += findMaxRightDepth(rebusNode.getRight());
            }
        }
        return rDepth;
    }

    public ArrayList<String> generate(String[] args) {
//        RebusGenerator rg = new RebusGenerator();
        System.out.println("In generate");
        int sentenceLength = 0;
        ArrayList<String> rebusList = new ArrayList<String>();
        for (String word : args) {
            if (Utils.isValid(word) && sentenceLength < Utils.MAX_SENTENCE_SIZE) {
                sentenceLength += word.length();
                RebusNode economicalRebus = null;
                for (RebusNode baseRebus : findBaseRebus(word)) {
                    baseRebus.setLeft(buildOptimalRebusNode(baseRebus.getLeft()));
                    String leftResidue = rebusWalker(baseRebus.getLeft());
    //                System.out.println("left residue : " + leftResidue);
                    if (findMaxRightDepth(baseRebus.getLeft()) % 2 == 0) {
                        baseRebus.getRight().setRebus(leftResidue + baseRebus.getRight().getRebus());
    //                    System.out.println("right  : " + baseRebus.getRight().getRebus());
                    }
                    baseRebus.getRight().setCost(Utils.findWordCost(baseRebus.getRight().getRebus()));
                    baseRebus.setRight(buildOptimalRebusNode(baseRebus.getRight()));
                    if (economicalRebus == null) {
                        economicalRebus = baseRebus;
                    } else if (economicalRebus.getCost() > baseRebus.getCost()) {
                        economicalRebus = baseRebus;
                    }
                }
                if (economicalRebus != null) {
                    System.out.println("about to get rebuslist");
                    rebusList.addAll(Utils.rebusPrintList(economicalRebus));
//                    System.out.println(word + " - optimal rebus : " + r);
                }
            } else {
                System.out.println(" Word : "+word+" is invalid or sentence exceeded max limit : "+Utils.MAX_SENTENCE_SIZE);
            }

        }

        return rebusList;
    }

    public static void main(String[] args) {
        RebusGenerator rg = new RebusGenerator();
        int sentenceLength = 0;
        for (String word : args) {
            if (Utils.isValid(word) && sentenceLength < Utils.MAX_SENTENCE_SIZE) {
                sentenceLength += word.length();
                RebusNode economicalRebus = null;
                for (RebusNode baseRebus : rg.findBaseRebus(word)) {
                    baseRebus.setLeft(rg.buildOptimalRebusNode(baseRebus.getLeft()));
                    String leftResidue = rg.rebusWalker(baseRebus.getLeft());
    //                System.out.println("left residue : " + leftResidue);
                    if (rg.findMaxRightDepth(baseRebus.getLeft()) % 2 == 0) {
                        baseRebus.getRight().setRebus(leftResidue + baseRebus.getRight().getRebus());
    //                    System.out.println("right  : " + baseRebus.getRight().getRebus());
                    }
                    baseRebus.getRight().setCost(Utils.findWordCost(baseRebus.getRight().getRebus()));
                    baseRebus.setRight(rg.buildOptimalRebusNode(baseRebus.getRight()));
                    if (economicalRebus == null) {
                        economicalRebus = baseRebus;
                    } else if (economicalRebus.getCost() > baseRebus.getCost()) {
                        economicalRebus = baseRebus;
                    }
                }
                if (economicalRebus != null) {
                    String r = Utils.rebusPrinter(economicalRebus);
                    System.out.println(word + " - optimal rebus : " + r);
                }
            } else {
                System.out.println(" Word : "+word+" is invalid or sentence exceeded max limit : "+Utils.MAX_SENTENCE_SIZE);
            }

        }
    }
}


//        RebusNode rn = rg.findSecondaryRebus(word);
//        String r = Utils.rebusPrinter(rn);
//        System.out.println("The final rebus : " + r);


//    public void setRightWalkerRecursionDepth(int rightWalkerRecursionDepth) {
//        this.rightWalkerRecursionDepth = rightWalkerRecursionDepth;
//    }
//
//    public int getRightWalkerRecursionDepth() {
//        return rightWalkerRecursionDepth;
//
//    }

//    private RebusNode findSecondaryRebus (String word) {
//        HashSet<String> picSet = findUniquePictureSet(word);
//        RebusNode nextRn = null;
//        for (Iterator it = picSet.iterator(); it.hasNext(); ) {
//            String pic = (String) it.next();
//            LCSCell[][] lcsTable = Utils.computeLCS(word, pic);
//            String lcs = Utils.printLCS(lcsTable, word, word.length(), pic.length()).reverse().toString();
//
//            nextRn = Utils.getRebusNode(word, lcs, pic);
////            System.out.println("Rebus : "+nextRn.getRebus());
//            if (word.equalsIgnoreCase(lcs)) {
//                nextRn = Utils.getRebusNode(word, lcs, pic);
//                if (nextRn.getRight() != null && nextRn.getRight().getRebus() != null
//                        && !"".equalsIgnoreCase(nextRn.getRight().getRebus())
//                        && nextRn.getRight().getRebus().length() > 1
//                        && nextRn.getCost() > 2) {
//                    RebusNode rightRn = findSecondaryRebus(nextRn.getRight().getRebus());
//                    nextRn.setRight(rightRn);
//                    nextRn.setCost(rightRn.getCost());
//                }
//            }
//        }
//        return nextRn;
//    }